/**
 *
 * 接雨水最多的, 其实, 就是找最近最高的那个柱子
 *
 */

// 双指针遍历
function maxWater(arr) {
    let left = 0, right = arr.length - 1, leftHeight = 0, rightHeight = 0, res = 0
    while (left < right) {
        if (arr[left] < arr[right]) {
            leftHeight = Math.max(arr[left], leftHeight)
            res += leftHeight - arr[left]
            left++
        } else {
            rightHeight = Math.max(arr[right], rightHeight)
            res += rightHeight - arr[right]
            right--
        }
    }
    return res;
}

const arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
console.log(maxWater(arr));


// 最简单的方式
function max(heights) {
    if (arr.length === 0) return null;
    let res = 0, l_max = 0, r_max = 0, n = arr.length

    for (let i = 1; i < n; i++) {
        l_max = 0;
        r_max = 0

        for (let j = i; j < n; j++) {
            r_max = Math.max(r_max, heights[i])
        }
        for (let j = i; i >= 0; j--) {
            l_max = Math.max(l_max, heights[j])
        }
        res += Math.min(r_max, l_max) - heights[i]
    }
    return res;
}


// 最简单的实现方式2
function maxArea(arr) {
    if (arr.length === 0) return 0;
    let l_max = [], r_max = [], n = arr.length, res = 0
    for (let i = 1; i < n; i++) {
        l_max[i] = Math.max(l_max[i - 1], arr[i])
    }
    for (let i = n - 1; i >= 0; i--) {
        r_max[i] = Math.max(r_max[i + 1], arr[i])
    }
    for (let i = 1; i < n; i++) {
        res += Math.min(l_max[i], r_max[i]) - arr[i]
    }
    return res
}


function maxAreaV2(heights) {
    let len = heights.length, res = [], l_max = 0, r_max = 0
    for(let i =0; i<len; i++) {

        for(let j=i; j<len; j++){
            r_max = Math.max(r_max, heights[j])
        }
        for(let j= i; i>0; j--){
            l_max = Math.max(l_max, heights[j])
        }
        res += Math.min(l_max, r_max) - heights[i]
    }
    return res;
}


